TOC 2 - Nondeterministic DFAs
December 29th, 2008 — 01:39 pmRecall from the last TOC entry that we defined DFAs and the languages that they recognized. I know that I promised to elaborate on the Pumping Lemma today, but I figured that Nondeterminism would be more interesting, and would also be a less awkward segue into the remaining topics in this model of computation. In addition, nondeterminism is a very important idea in itself, and is used very often with other models of computation. In fact, in the P vs NP problem, the “N” stands for “Nondeterministic”. Of course, in that case, we would be working with nondeterministic Turing Machines, but the idea of nondeterminism is essentially unchanged.
Nondeterminism
A Nondeterministic Finite Automata (NFA) is similar to a DFA, with two major differences:
- The transition arrows of an NFA can be labelled with the special symbol
. These are essentially blank “branching” symbols, and cause the NFA to “branch” into multiple copies of itself. Recall that when we simulate a DFA on an input, we keep track of the current state, read in the next symbol, follow the transition arrow labelled with that symbol, and move to the state that the arrow leads to. In an NFA, when we are at a state that has arrows labelled , we “split” into different copies of the machine in which we follow each of those arrows. Then, if any of those copies of the NFA accepts the string, then the NFA accepts. Equivalently, denote “keeping track of the current state” by marking the current state. Then, the current states of an NFA are all the marked states. If any marked state has an arrow with a label, we follow the arrow and label that state as well. When this -marking is done, we read in the next symbol of the input, and move our state markers as appropriate. This is basically a “parallel” program. - In a DFA, given a state
, there must be an outgoing arrow from that is labeled with every symbol in the input alphabet. This condition is not neccesary for an NFA. For example, say that a marked node has no arrows leading out of it. Then, when we read in the next input symbol, that node will become unmarked, and no new nodes will be marked. That “branch” of the computation is essentially allowed to “die”. In addition, states may have multiple outgoing arrows with the same label. If state q has arrows leading to x and y that are both labeled 0, then reading 0 while q is marked will mean that both x and y will be marked next. This is equivalent to branching on .
The nondeterministic branching can be viewed as a type of “guessing” action by the NFA. It tries to guess the correct paths to go down, and accepts if one of those is accepting. We can illustrate this with the following NFA:
As you can see, it accepts all strings that contain a “11″ or a “101″ somewhere.
It’s generally easier to define NFA’s to accept a certain language 
than to define a DFA to do it. After all, NFAs can do everything that a DFA can, with the additional possibility of guessing branches. However, it turns out that the class of languages that NFAs and DFAs recognize is the same - that is, for every DFA, there is an equivalent NFA that recognizes the same language (and vice versa). One direction of this conversion is obvious: given a DFA, the equivalent NFA is the same as the DFA. However, we have to show that for an arbitrary NFA, we can construct a DFA to recognize the exact same language. This is more difficult.
Theorem: Given an NFA 
, there exists a DFA 
such that 
, where 
where 
is an automaton denotes the language recognized by .
Proof: We can approach this by construction. We will simply construct a DFA that recognizes the same language as the NFA. Let 
be the power set of 
; that is, the set of all the subsets of . This move should give you a good idea of where we’re going. Say that we are running 
on some input, and have states 
marked. When we read the next symbol, we move the markers on all those states, until we have another set of marked states, 
that are marked. But this defines our transition function exactly! Given a subset of states in the NFA, our transition function in the DFA will, upon reading a symbol, transition to the set of states that would have resulted from feeding that symbol into the NFA. The start state will simply be the sub containing the start state of the NFA, and the accept states 
will be all the subsets that contain at least one accept state in the NFA. It is easy to see that this DFA will then recognize the same language as the given NFA.
This equivalence of DFA and NFA will come in use next time, when we talk about Regular Expressions, and some of their properties. Until then, a few problems to whet your appetite for NFA fun!
- Give an NFA that recognizes {w | w ends with 00}
- Give an NFA that recognizes { w | w contains even number of 0s, or exactly two 1s} (using only six states)
problem is from, and is a very active area of research.
. They are defined as follows:
is the input alphabet of the machine. In other words, it is a set of symbols that the machine can take in, and make appropriate state transitions based on the input. Usually, the choice of alphabet does not matter too much, and we use 
, because you can encode any alphabet into those two symbols anyway. However, when we get into nondeterminism (which we’ll do shortly), we can also take another symbol, the empty string 
is the transition function of the DFA. It is a function 
; given a state and a symbol of the input alphabet, it tells what state to transition to.
is the start state of the machine. When reading an input, you start from this state.
